package algorithm.leetcode;

import java.util.Arrays;

/***
 * 找到输入数组字典序中的下一个位置，感觉像是找规律一样.....
 * （可以多举几个例子，找一下其中的共同点）
 * 比如1，2，3，4，5的下一个字典序为1，2，3，5，4 可以看到只改变了最后两个数字，因为整个序列都是升序的
 * 再比如1，5，4，3，2的下一个字典序为2，5，4，3，1 可以看到5，4，3，2是降序的，
 * 就需要找到比1的大的最小数字2，和1交换位置，然后后面的升序排序
 * 于是，从中总结出规律，需要先找到左右两个下标left和right，left表示最后一组的升序数字的第1个，
 * right表示left后面的数字中比l大的最靠右的数字，
 * 比如 1，2，3，4，5 -> left = 4 , right = 5     1，5，4，3，2 -> left = 1 , right= 2
 * 然后，将left和right位置的数字交换，交换后，对left后面部分的数字进行升序排序即可
 */
public class LeetCode_31_nextPermutation {
    public void nextPermutation(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                l = i;
            }
        }
        for (int i = l + 1; i < nums.length; i++) {
            if (nums[i] > nums[l]) {
                r = i;
            }
        }
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
        Arrays.sort(nums, l + 1, nums.length);
        return;
    }

    public static void main(String[] args) {

    }

}
